#include <stdio.h>
#include <cstdlib>

#define MaxSize 5
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

void InitQueue(SqQueue &Q){
    Q.rear = Q.front = 0;
}

bool isEmpty(SqQueue &Q){
    if(Q.rear == Q.front){
        return true;
    } else{
        return false;
    }
}

//入队操作
bool EnQueue(SqQueue &Q,ElemType x){
    //使用一个空间来区分队列的满与空，当首指针在尾指针的后一位时为满
    if((Q.rear + 1)%MaxSize == Q.front){
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;//这是个循环数组，所以在确定位置时一定要使用取余符号
    return true;
}

//出队操作
bool DeQueue(SqQueue &Q,ElemType &x){
    //如果队列为空
    if(Q.rear == Q.front){
        return false;
    }
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}
//_______________________________________
//以下是链表实现队列,这是一条带有头结点的单链表

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
//不能删去第一个LinkeNode，因为你在类中使用了这个类名

typedef struct {
    LinkNode *front,*rear;
}LinkQueue;

void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));//头节点
    Q.front->next = NULL;
}

bool isEmpty(LinkQueue Q){
    if(Q.front == Q.rear){
        return true;
    } else{
        return false;
    }
}

//入队
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode *) malloc(sizeof (LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}

//出队、头部删除法
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front == Q.rear){
        return false;
    }
    LinkNode *p = Q.front->next;//头节点什么也没有，只有下一个节点才有数据
    x = p->data;
    Q.front->next = p->next;
    //如果删除的是最后一个元素，则将队列置为空
    if(Q.rear == p){
        Q.rear = Q.front;
    }
    free(p);
    return true;
}


int main() {

    return 0;
}
